package code;

import java.util.Date;
import java.util.Scanner;

public class NUM_day16 {
    static final int MOD=1000000007;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        while (T-- > 0) {
            int N = sc.nextInt();
            int   result=   GetResult(N);
            System.out.println(result);
        }
    }
    public static int GetResult(int n ) {
        int[][][] dp = new int[n+1][7][7];
        for (int i = 1; i <= 9; i++) {
            dp[1][i%7][i%7] ++;
        }
        for (int i = 1; i <n; i++) {
            for(int sum=0;sum<7;sum++){
                for(int mul=0;mul<7;mul++){
                    if(dp[i][sum][mul]==0)continue;
                    for(int j=0;j<=9;j++){
                        int newSum=(sum+j)%7;
                        int newMul=(mul*j)%7;
                        dp[i+1][newSum][newMul]=(dp[i+1][newSum][newMul]+dp[i][newSum][newMul])%MOD;
                    }
                }
            }
        }
        return dp[n][0][0];
    }
}
